P3911 最小公倍数之和

简单问题复杂化是解决问题的一个好方法。

令 $c_i$ 表示 $i$ 出现的次数，$n$ 为最大数字。

$\sum_{i=1}^n \sum_{j=1}^nc_i \times c_j \times lcm(i,j)$

$\sum_{i=1}^n \sum_{j=1}^nc_i \times c_j \times \frac{i \times j}{gcd(i,j)}$

$\sum_{k=1}^n\sum_{i=1}^n \sum_{j=1}^n [gcd(i,j)=k] c_i \times c_j \times \frac{i \times j}{k}$

$\sum_{k=1}^n\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{k} \rfloor} [gcd(i,j)=1] c_{ik} \times c_{jk} \times i \times j \times k$

$\sum_{k=1}^n\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{d|gcd(i,j)}\mu(d) \times c_{ik} \times c_{jk} \times i \times j \times k$

$\sum_{k=1}^n\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor} \mu(d) \times d^2 \sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{kd} \rfloor} c_{ikd} \times c_{jkd} \times i \times j \times k$

$\sum_{k=1}^n\sum_{kd=1}^{n}\mu(d) \times d^2\sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{kd} \rfloor} c_{ikd} \times c_{jkd} \times i \times j \times k$

$\sum_{T=1}^n T(\sum_{d|T}\mu(d) \times d )\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{T} \rfloor} c_{iT} \times c_{jT} \times i \times j$

$\sum_{T=1}^n T(\sum_{d|T}\mu(d) \times d ) (\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor } c_{iT} \times i)^2$

第一个括号预处理，第二个括号直接暴力算。

预处理和查询复杂度均为 $\Theta(n \ln n)$。

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 5e4;
int n , m , k , cnt[ MAXN + 5 ] , prime[ MAXN + 5 ] , mu[ MAXN + 5 ];
long long Ans , f[ MAXN + 5 ];
bool vis[ MAXN + 5 ];

void sieve( ) {
	mu[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) {
			prime[ ++ k ] = i;
			mu[ i ] = -1;
		}
		for( int j = 1 ; j <= k && i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) break;
			mu[ i * prime[ j ] ] = -mu[ i ];
		}
	}
    for( int i = 1 ; i <= MAXN ; i ++ )
        for( int j = i ; j <= MAXN ; j += i )
            f[ j ] += i * mu[ i ];
}

int main( ) {
	sieve( );
	scanf("%d",&n);
	for( int i = 1 , x ; i <= n ; i ++ )
		scanf("%d",&x) , cnt[ x ] ++ , m = max( m , x );
	n = m;

    for( int i = 1 ; i <= n ; i ++ ) {
        long long tmp = 0;
        for( int j = 1 ; j <= n / i ; j ++ )
            tmp += 1ll * cnt[ i * j ] * j;
        Ans += i * f[ i ] * tmp * tmp;
    }
    printf("%lld", Ans );
	return 0;
}